/*
 * @lc app=leetcode.cn id=1071 lang=cpp
 *
 * [1071] 字符串的最大公因子
 */

// 大数计算

// @lc code=start
class Solution {
public:
    // 定义一个函数, 用于检查是否可以除尽
    bool fun(string s, string t)
    {
        // 首先两个字符串长度不能整除的话, 字符串一定不能整除
        int length_s = static_cast<int>(s.length()) / static_cast<int>(t.length());
        string ans = "";
        for(int i = 0; i < length_s; ++i)
        {
            ans += t;
        }
        return ans == s;
    }

    string gcdOfStrings(string str1, string str2) {
        int len_str1 = static_cast<int>(str1.length()), len_str2 = static_cast<int>(str2.length());

        // 从大到小开始遍历
        for(int i = min(len_str1, len_str2); i > 0; --i)
        {   
            // 首先要两个字符串都能整除这小段字符串
            if(len_str1 % i == 0 && len_str2 % i == 0)
            {
                string temp = str1.substr(0, i);
                // 取值str1或者str2都可以, 不需要区分.
                if(fun(str1, temp) && fun(str2, temp))
                {
                    return temp;
                }
            }
        }
        return "";
    }
};
// @lc code=end

